\documentclass{beamer}
\usepackage[english]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage{microtype}
\usepackage{graphicx}
\usepackage{bbm}
\usetheme{Frankfurt}
\title{Quantum computation}
\author{Franck Duriez and Charles Pelletier}
\date{\today}

% Macros
\input{macro}

\begin{document}

\begin{frame}
\titlepage
\end{frame}

\begin{frame}{What is quantum computation?}
	\begin{itemize}
		\item Born in the 1970s.
		\item Use quantum physics results applied to computer science.
		\item Interaction between \textit{qubits}.
		\item Has a huge potential for calculating faster than classical computers.
\end{itemize}
\end{frame}

\begin{frame}{Qubits}
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=5cm]{qubit.eps}
		\caption{Representation of a qubit compared to a classical bit and a probabilistic bit}
	\end{figure}
\end{frame}

\begin{frame}{n-Qubits : Here is the difference}
	\newcommand{\Cnbit}{\includegraphics[scale=0.5]{classicbit.eps}}
	\newcommand{\Pnbit}{\includegraphics[scale=0.5]{probbit.eps}}
	\newcommand{\Qnbit}{\includegraphics[scale=0.25]{hypersphere.eps}}
	\centering{
	\begin{tabular}{ccc}
		\begin{tabular}{ccc}
			\Cnbit & \Cnbit & \Cnbit \\
			\Cnbit & \Cnbit & \Cnbit 
		\end{tabular} \hspace*{0.4cm} &
		\begin{tabular}{ccc}
			\Pnbit & \Pnbit & \Pnbit \\
			\Pnbit & \Pnbit & \Pnbit 
		\end{tabular} &
		\begin{tabular}{c}
			\Qnbit
		\end{tabular} \\
		Classical n-bit \hspace*{0.4cm} & Probabilistic n-bit & n-Qubit
	\end{tabular}
	}

	\vspace*{0.5cm}

	One n-qubit represents the memory state but also the current quantum entanglement of the system.
\end{frame}

\begin{frame}{The entaglement is the key. Example :}
	Let $L$ be a list of $n$ integers without structure. We want to find all the elements $x$ in $L$ that verify a property $P$.	
	\begin{itemize}
		\item<1-> In a classical way, you need to see each element of the list to find them.
		\item<2-> And so, the time-complexity is at least $n$.
		\item<3-> Because of the entaglement, a quantum algorithm doesn't need to see each element.
		\item<4-> The Grover's algorithm can solve this problem with a $\sqrt{n}$ time-complexity. 
	\end{itemize}
\end{frame}

\begin{frame}{Logical gates}
	\begin{itemize}
		\item<1-> For a system consisting of $n$ qubits, state functions are in the Hilbert space $\compx^{2n}$.
		\item<2-> A gate is a unitary operator $\compx^{2n} \longrightarrow \compx^{2n}$.
		\item<3-> Therefore operators are reversible, contrary to classic gates.
		\item<4-> Physicists claim that quantum physics can explain all of classic physics' issues.
		\item<5-> Any classical logical gate should then be buildable from a set of quantum gates.
	\end{itemize}
\end{frame}

\begin{frame}{The main logical gates}
	\begin{tabular}{cc}
		\begin{tabular}{c}
			\includegraphics[width=3cm]{Porte_01.eps} \\
			\includegraphics[width=5cm]{Porte_02.eps} \\
		\end{tabular} &
		\begin{tabular}{c}
			\includegraphics[width=5cm]{Porte_03.eps}
		\end{tabular}
	\end{tabular}
\end{frame}

\begin{frame}{Example : The NAND gate.}
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=5cm]{example_01.eps}
		\caption{Truth table for the Toffoli gate, and its circuit representation.}
	\end{figure}
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=5cm]{example_02.eps}
		\caption{Classical circuit implementating a NAND gate using Toffoli gate.}
	\end{figure}
\end{frame}

\begin{frame}{What does it look like in the end?}
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=7cm]{quantum2.eps}
		\caption{Quantum computer scheme.}
	\end{figure}
\end{frame}

\begin{frame}{Applications to high-speed calculations.}
	\begin{itemize}
		\item<1-> Quantum computers are built in a different way (e.g. reversible gates).
		\item<2-> Such a system architecture exponentially decreases the lenght of calculations.
		\item<3-> One example is Shor's algorithm, which provides integer factorization with a $O((\log{n})^3)$ time-complexity and a $O(\log{n})$ space-complexity versus a non-polynomial complexity in a classical way.
	\end{itemize}
\end{frame}

\begin{frame}{Shor's algorithm}
	\begin{itemize}
		\item<1-> Shor's algorithm can calculate very large numbers' integer factorization much faster than classical algorithms.
		\item<2-> This program threatens current cryptography (notably RSA system), because factorizing a 300-digit number could be done in less than a second.
		\item<3-> RSA cryptography system is currently used in almost all crypted communications worldwide (credit card numbers, crypted e-mails, etc.).
		\item<4-> \textbf{But} quantum computation would be able to provide a new cryptographic system which could not be hacked.
	\end{itemize}
\end{frame}

\begin{frame}{Quantum teleportation}
	Quantum teleportation uses entanglement between two particles to transmit information.
	Let Alice and Bob be two people wanting to communicate. Assume Alice wants to send Bob a message.

	\vspace*{1cm}

	\begin{tabular}{cc}
		\includegraphics[width=7cm]{teleportation.eps} &
		\includegraphics[width=3cm]{quantum.eps}
	\end{tabular}
\end{frame}

\end{document}
